package club.babyf.nativeai.demo.algorithm;

/**
 * QuickSort.
 *
 * @author zhanglei.
 * @date 2025/4/12 11:57.
 * @description 快速排序.
 */
public class _9_QuickSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 6, 7, 9, 1, 2};
        _9_QuickSort quickSort = new _9_QuickSort();
        quickSort.print(arr);
        quickSort.quickSort(arr);
        quickSort.print(arr);
    }

    private void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i);
        }
        System.out.println();
    }

    private void quickSort(int[] arr) {
        doQuickSort(0, arr.length - 1, arr);
    }

    private void doQuickSort(int low, int high, int[] arr) {
        if (low < high) {
            int parIndex = partition(low, high, arr);
            doQuickSort(low, parIndex - 1, arr);
            doQuickSort(parIndex + 1, high, arr);
        }
    }

    private int partition(int low, int high, int[] arr) {
        int i = low - 1;
        int par = arr[high];
        for (int j = low; j < high; j ++) {
            if (arr[j] <= par) {
                i++;
                swap(i, j, arr);
            }
        }
        swap(i + 1, high, arr);
        return i + 1;
    }

    private void swap(int i, int j, int[] arr) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
